package com.sicheng.lc.杂题.滑动窗口专题;

import java.util.HashMap;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/8/3 10:25
 */
public class K个不同整数的子数组 {
    //https://leetcode.cn/problems/subarrays-with-k-different-integers/
    public int subarraysWithKDistinct(int[] nums, int k) {
        return cnt(nums, k) - cnt(nums, k - 1);
    }

    // 与数位dp，前缀和处理区间问题类似
    // 对于区间[l,r]问题 常常会处理成 f(r) - f(l - 1)
    // 转化成求取 小于等于k条件的问题
    // 此题而言直接就转成了 元素类型小于等于k的子数组个数
    private int cnt(int[] nums, int k) {
        int res = 0;

        HashMap<Integer, Integer> map = new HashMap<>(k << 1);
        for (int r = 0, l = 0; r < nums.length; r++) {
            map.put(nums[r], map.getOrDefault(nums[r], 0) + 1);

            while (l <= r && map.size() > k) {
                int x = map.get(nums[l]);
                map.put(nums[l], x - 1);
                if (x - 1 == 0)
                    map.remove(nums[l]);
                l++;
            }
            res += r - l + 1;
        }

        return res;
    }
}
